/**
 * @(#) secondLargest.java Jan 11, 2010 1:42:29 PM
 *      Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 *      All right reserved
 */
package old;

/**
 * Class <code>secondLargest</code>
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Jan 11, 2010 1:42:29 PM
 * 
 */
public class secondLargest
{

  public int count = 0;

  public int[] getSec(int[] data, int start, int end)
  {
    if (end - start <= 1) {
      if (data[start] < data[end]) {
        count++;
        return new int[] { data[end], data[start] };
      }
      else {
        count++;
        return new int[] { data[start], data[end] };
      }
    }

    int[] left = getSec(data, start, start + (end - start) / 2);
    int[] right = getSec(data, start + (end - start) / 2 + 1, end);
    int[] current = new int[2];
    if (left[0] > right[0]) {
      count++;
      current[0] = left[0];
      if (right[0] > left[1]) {
        count++;
        current[1] = right[0];
      }
      else {
        count++;
        current[1] = left[1];
      }

    }
    else {
      count++;
      current[0] = right[0];
      if (right[1] > left[0]) {
        count++;
        current[1] = right[1];
      }
      else {
        count++;
        current[1] = left[0];
      }
    }
    return current;

  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    int data[] = new int[] { 2, 5, 8, 37, 3, 9, 1, 6, 12, 15, 18, 17, 13, 19,
        11, 16, 22, 25, 28, 27, 23, 29, 21, 26, 32, 35, 38, 34, 33, 39, 31, 36 };
    secondLargest sl = new secondLargest();
    int newdata[] = sl.getSec(data, 0, data.length - 1);
    System.out.println(data.length + " " + newdata[0] + " " + newdata[1] + " "
        + sl.count);
  }

}
